package com.ai.zuochengyun.phase01.class07;

import java.util.ArrayList;
import java.util.List;

/**
 * 字符串全排列
 */
public class Code04_PrintAllPermutation {

    public static void main(String[] args) {
        String str = "acc";
        List<String> ans = permutation1(str);
        for (String s : ans) {
            System.out.println(s);
        }

        System.out.println("==============");
        List<String> ans2 = permutation2(str);
        for (String s : ans2) {
            System.out.println(s);
        }

        System.out.println("==============");
        List<String> ans3 = permutation3(str);
        for (String s : ans3) {
            System.out.println(s);
        }
    }

    public static List<String> permutation1(String str) {
        List<String> ans = new ArrayList<>();

        // 还剩余的字符
        List<Character> rest = new ArrayList<>();
        char[] chars = str.toCharArray();
        for (char ch : chars) {
            rest.add(ch);
        }
        // 之前的决定
        String path = "";
        // 定义递归函数
        process1(rest, path, ans);
        return ans;
    }

    private static void process1(List<Character> rest, String path, List<String> ans) {
        // base case
        if (rest.isEmpty()) {
            // 没有值后，将之前选在的路径加入结果集中
            ans.add(path);
        } else {
            int n = rest.size();
            for (int i = 0; i < n; i++) {
                Character c = rest.get(i);
                rest.remove(c);
                process1(rest, path + c, ans);
                // 还原现场
                rest.add(i, c);
            }
        }
    }


    public static List<String> permutation2(String str) {
        List<String> ans = new ArrayList<>();

        char[] chars = str.toCharArray();
        // 之前的决定
        String path = "";
        // 定义递归函数
        process2(chars, 0, ans);
        return ans;
    }

    private static void process2(char[] chars, int index, List<String> ans) {
        // 下标越界后，表明字符已经判断结束了，那么将之前的路径放入结果集中
        if (index == chars.length) {
            ans.add(String.valueOf(chars));
        } else {
            // 0和0交换 1和1交换 2和2交换
            // 0和1交换
            // 0和2交换
            for (int i = index; i < chars.length; i++) {
                // 当前位置index和i进行交换
                swap(chars, index, i);
                // 跑所有的支路
                process2(chars, index + 1, ans);
                // 恢复现场
                swap(chars, index, i);
            }
        }
    }

    private static void swap(char[] chars, int index, int i) {
        char temp = chars[index];
        chars[index] = chars[i];
        chars[i] = temp;
    }


    public static List<String> permutation3(String str) {
        List<String> ans = new ArrayList<>();

        char[] chars = str.toCharArray();
        // 之前的决定
        String path = "";
        // 定义递归函数
        process3(chars, 0, ans);
        return ans;
    }

    private static void process3(char[] chars, int index, List<String> ans) {
        if (index == chars.length) {
            ans.add(String.valueOf(chars));
        } else {
            boolean[] visited = new boolean[256];
            for (int i = index; i < chars.length; i++) {
                // 提前剪枝，不用后续逻辑
                if (!visited[chars[i]]) {
                    visited[chars[i]] = true;
                    swap(chars, index, i);
                    process3(chars, index + 1, ans);
                    // 恢复现场
                    swap(chars, index, i);
                }
            }
        }
    }
}
